package BinaryTree;

import test0ne.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author zhang lei
 * @Date 2021-11-23 13:01
 * 展平二叉搜索树
 *
 * 二叉搜索树：  左孩子 <= root <= right
 */
public class Algo_Offer52 {
    public static void main(String[] args) {
        TreeNode root= new TreeNode(5);
        root.left = new TreeNode(1);
//        root.left.left = new TreeNode(1);
//        root.left.right = new TreeNode(3);
        root.right = new TreeNode(7);
//        root.right.left = new TreeNode(6);
//        root.right.right = new TreeNode(7);
        System.out.println(kai(root).toString());
    }

    public static TreeNode kai(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        //todo  prev节点是设置， 到达最根节点的时候  将右边整棵树中序遍历，然后接到最前面的节点
        TreeNode prev = null;
        TreeNode first = null;

        while (cur!=null || !s.isEmpty()) {
            //先走到最左边
            while (cur != null) {
                s.push(cur);
                cur = cur.left;
            }

            cur = s.pop();
            if(prev != null) {
                prev.right = cur;
            }else {
                first = cur;
            }

            cur.left = null;
            cur = cur.right;
            prev = cur;


        }
        return first;
    }
}
